package com.datastructure.test.deleteduplicatelistnode;

import java.util.ArrayList;

public class DeleteDuplicateLinkedList {
    ArrayList<Integer> res = new ArrayList<>();
    ArrayList<Integer> temp = new ArrayList<>();
    public static void main(String[] args) {
        ListNode listNode=new ListNode();
        listNode.val=1;
        ListNode listNode1 = new ListNode();
        listNode1.val=2;
        ListNode listNode2 =new ListNode();
        listNode2.val=2;
        listNode.next=listNode1;
        listNode1.next=listNode2;
        DeleteDuplicateLinkedList deleteDuplicateLinkedList = new DeleteDuplicateLinkedList();
        System.out.println(deleteDuplicateLinkedList.deleteDuplicates(listNode));
    }

    public ListNode deleteDuplicates (ListNode head) {
        // write code here
        ListNode cur = null;
        ListNode resTemp = null;
        while (head!=null){
            if(res.contains(head.val)){
                temp.add(head.val);
            }else {
                res.add(head.val);
            }
            head=head.next;
        }
        for (int i = res.size()-1; i >=0; i--) {
            if(!temp.contains(res.get(i))){
                cur = new ListNode();
                cur.val=res.get(i);
                cur.next=resTemp;
                resTemp=cur;
            }
        }
        return cur;
    }

    public ListNode deleteDuplication(ListNode pHead) {
        ListNode node = new ListNode(0);
        node.next = pHead;
        ListNode next;
        ListNode cur = pHead;
        ListNode pre = node;
        while (cur != null) {
            next = cur.next;
            boolean tmp = false;
            while (next != null && cur.val == next.val) {
                next = next.next;
                pre.next = next; // 前一个不同节点指向下一个不同节点
                tmp = true;
            }
            if (!tmp) { // 如果以前没有相同的节点，则pre指向当前节点，保证下次遇到相同的节点设置next
                pre = cur;
            }
            cur = next;
        }
        return node.next;
    }

}

class ListNode {
    int val;
    ListNode next = null;

    public ListNode() {
    }

    public ListNode(int val) {
        this.val = val;
    }
}
